一、題目介紹
今天要解的題目是LeetCode的Merge Intervals

題目會給我們一個由許多區間組成的陣列，每個區間都有開始位置與結束位置
例如：intervals = [[1,3],[2,6],[8,10],[15,18]]

如果兩個區間有重疊，就需要將它們合併
例如：[1,3] 和 [2,6]
兩個區間有重疊，因此可以合併成[1,6]
最後結果為[[1,6],[8,10],[15,18]]

題目的重點就是：將所有互相重疊的區間合併，並回傳不重疊的區間集合。

二、解題思路
這題如果直接從每個區間開始互相比較，會需要處理很多不同的情況
因此，我們可以先使用Sorting將所有區間按照「開始位置」由小到大排序

例如原本[[8,10],[1,3],[15,18],[2,6]]
排序後[[1,3],[2,6],[8,10],[15,18]]
這樣排列之後，我們就可以從左到右依序檢查

判斷是否重疊
假設目前已經合併到[1,3]
下一個區間是[2,6]
因為2 <= 3
代表下一個區間的開始位置沒有超過目前區間的結束位置，所以兩個區間有重疊

因此可以合併[1, max(3,6)]
得到[1,6]
接著繼續檢查下一個區間

如果沒有重疊呢？
例如目前區間[1,6]
下一個區間[8,10]
因為8 > 6
代表兩個區間沒有重疊

因此[1,6]可以直接加入結果，然後開始處理新的[8,10]

三、解題流程
以以下為例
[[1,3],[2,6],[8,10],[15,18]]

首先按照開始位置排序[[1,3],[2,6],[8,10],[15,18]]
接著依序處理

最後得到[[1,6],[8,10],[15,18]]

這題最重要的觀念可以濃縮成一句話：先排序，再從左到右判斷目前區間與下一個區間是否重疊。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 排序需要：O(n log n)
• 之後只需要從頭到尾掃描一次：O(n)
• 因此整體時間複雜度為：O(n log n)
• 空間方面，除了輸出結果以外，主要需要排序與結果儲存空間，因此可以視實作與輸出需求描述為：O(n)

Python

• Python使用：intervals.sort()
• 排序時間複雜度為：O(n log n)
• 之後進行一次線性掃描：O(n)
• 所以整體時間複雜度為：O(n log n)
• 結果陣列最多可能存放n個區間，因此空間複雜度為：O(n)

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天學習的Merge Intervals讓我了解到，排序不只是單純將資料由小到大排列，而是可以透過排序讓資料之間的關係變得更加容易處理。

如果沒有排序，判斷區間是否重疊時需要考慮很多不同的排列情況；但將區間按照開始位置排序後，只需要從左到右依序比較，就可以有效率地完成合併。

這題也讓我更加理解Sorting + Greedy的解題方式。先透過排序建立規律，再利用目前區間的結束位置判斷下一個區間是否能夠合併。

今天最大的收穫是：有時候先把資料整理好，後面的問題就會簡單很多。

這也讓我注意到，在寫程式時，選擇適合的資料處理方式往往比直接開始寫程式更加重要。